#include <stdio.h>
#include <stdlib.h>
#include <utility>

using namespace std;

typedef struct Node {
		int val;

	struct Node * next;
} Node;

typedef struct LinkedList {
	Node * head;
} LinkedList;

typedef struct hash_table {
	int size;
	Node ** table;
} HashTable;

void print(LinkedList & l) {
	for(Node * n = l.head; n != NULL; n = n->next)
		printf("%d ", n->val);
	printf("\n");
}

void print(HashTable & ht) {
	printf("Hash Table Size: %d\n", ht.size);
	for (int i = 0; i < ht.size; ++i) {
		Node * runner = ht.table[i];
		if (runner) {
			for (;runner != NULL; runner = runner->next) {
				printf("%d ", runner->val);
			}
			printf("\n");
		}
	}
}

int hash(HashTable & ht, int val) {
	return 	val%ht.size;
}

bool findInHashTable(HashTable & ht, int val) {
	int idx = hash(ht, val);
	for (Node * runner = ht.table[idx]; runner != NULL; runner = runner->next) {
		if (runner->val == val)
			return true;
	}
	return false;
}

void appendToHead(LinkedList & l, int value) {
	Node * newnode = (Node *) malloc(sizeof(Node));
	newnode->val = value;
	newnode->next = NULL;

	if (l.head == NULL) {
		l.head = newnode;
		return;
	}
	
	newnode->next = l.head;
	l.head = newnode;
}

void addIntoHashTable(HashTable & ht, int val) {
	int idx = hash(ht, val);
	Node * newnode = (Node *) malloc(sizeof(Node));
	newnode->val = val;
	newnode->next = NULL;

	if (ht.table[idx] == NULL) {
		ht.table[idx] = newnode;
		return;
	}
	
	newnode->next = ht.table[idx];
	ht.table[idx] = newnode;
}


std::pair<Node *, bool> areIntersect(LinkedList & l1, LinkedList & l2) {
	if (l1.head == NULL || l2.head == NULL)
		return make_pair((Node *)0, false);
	//append l2 to the tail of l1
	Node * tail = l1.head;
	while(tail->next != NULL) tail = tail->next;
	tail->next = l2.head;

	//test if the combined list l1->l2 has a cycle, if yes, then l1 and l2 intersect; else they are disjoined.
	Node * slow = l1.head, * fast = l1.head;

	while(fast != NULL && fast->next != NULL) {
		slow = slow->next;
		fast = fast->next->next;
		if (slow == fast) {
			break;
		}
	}

	if (slow == fast) {
		fast = l1.head;
		//slow and fast, walking at the same rate, would finally reach a point, and this point is the starting node of the cycle, 
		//i.e., the node where two linked lists intersect.

		while(slow != fast) {
			slow = slow->next;
			fast = fast->next;
		}

		return make_pair(fast, true);
	}

	return make_pair((Node *)0, false);
}

bool areIntersect2(LinkedList & l1, LinkedList & l2) {
	if (l1.head == NULL || l2.head == NULL)
		return false;

	//initialize a hash_table
	HashTable ht1 = {.size = 100,
		       	.table = NULL 
		       };

	ht1.table = (Node **) malloc(sizeof(Node*) * ht1.size);
	for (int i = 0; i < ht1.size; ++i)
		ht1.table[i] = NULL;
	
	//map each element in l1 to the hash table
	for (Node * runner = l1.head; runner != NULL && !findInHashTable(ht1, runner->val); runner = runner->next)
		addIntoHashTable(ht1, runner->val);

	//initialize a hash_table
	HashTable ht2 = {.size = 100,
		       	.table = NULL 
		       };

	ht2.table = (Node **) malloc(sizeof(Node*) * ht2.size);
	for (int i = 0; i < ht2.size; ++i)
		ht2.table[i] = NULL;
	
	//map each element in l2 to the hash table
	for (Node * runner = l2.head; runner != NULL && !findInHashTable(ht2, runner->val); runner = runner->next)
		addIntoHashTable(ht2, runner->val);

	print(ht1);
	print(ht2);
	
	for(int i = 0; i < ht1.size; ++i) {
		for (Node * runner = ht1.table[i]; runner != NULL; runner = runner->next) {
			if (findInHashTable(ht2,runner->val)) {
				free(ht1.table);
				free(ht2.table);
				return true;	
			}
		}
	}

	//deconstruct the hash table
	free(ht1.table);
	free(ht2.table);
	return false;
}


int main ()
{
	LinkedList l1, l2;
	l1.head = l2.head = NULL;
	Node * n = (Node *)malloc(sizeof(Node));
	n->val = 100;
	n->next = NULL;
	
//Uncomment this line to make l1 and l2 intersect at n	
	l1.head = l2.head = n;

	for (int i = 0; i < 10; ++i) {
		int v1 = rand()%100 + 1;
		int v2 = rand()%100 + 1;
		appendToHead(l1, (i<<1)+1);
		appendToHead(l2, (i<<1));
	}
	
	print(l1);
	print(l2);

// using two pointers
	pair<Node *, bool> p = areIntersect(l1,l2);
	if (p.second) {
		printf("l1 and l2 are intersect!\n");
		printf("at node: %d\n", p.first->val);
	}
	else
		printf("l1 and l2 are disjoined!\n");

// using hash table
/*	
	if (areIntersect2(l1, l2))
		printf("l1 and l2 are intersect!\n");
	else
		printf("l1 and l2 are disjoined!\n");
*/	
	return 0;
}
